dinic(无当前弧优化)
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e4+7,M = 2e5+7,INF = 1 << 29;
int edge[M],succ[M],cap[M],ver[N],idx = 1;
int n,m,s,t,d[N],now[M];
int incf[N],maxflow;
queue<int> q;
void add(int u,int v,int w)
{
edge[++idx] = v;
cap[idx] = w;
succ[idx] = ver[u];
ver[u] = idx;
edge[++idx] = u;
cap[idx] = 0;
succ[idx] = ver[v];
ver[v] = idx;
}
bool bfs()
{
memset(d,0,sizeof d);
while(q.size()) q.pop();
q.push(s);d[s] = 1;now[s] = ver[s];
while(!q.empty())
{
int u = q.front();q.pop();
for(int i = ver[u];i;i = succ[i])
{
int v = edge[i];
if(cap[i] && !d[v])
{
q.push(v);
now[v] = ver[v];
d[v] = d[u] + 1;
if(v == t) return 1;
}
}
}
return 0;
}
int dinic(int u,int flow)
{
if(u == t) return flow;
int rest = flow,k,i;
for(int i = ver[u];i && rest;i = succ[i])
{
int v = edge[i];
if(cap[i] && d[v] == d[u] + 1)
{
k = dinic(v,min(rest,cap[i]));
if(!k) d[v] = 0;
cap[i] -= k;
cap[i ^ 1] += k;
rest -= k;
}
}
now[u] = i;
return flow - rest;
}
int main()
{
scanf("%d%d%d%d",&n,&m,&s,&t);
while(m--)
{
int u,v,c;scanf("%d%d%d",&u,&v,&c);
add(u,v,c);
}
int flow = 0;
while(bfs())
while(flow = dinic(s,INF))
maxflow += flow;
printf("%d",maxflow);
return 0;
}
EK
const int N = 1005,M = 2e5+7,INF = 1 << 29;
int edge[M],succ[M],cap[M],ver[N],idx = 1;
int n,m,s,t,st[N],pre[N];
ll incf[N],maxflow;
void add(int u,int v,int w)
{
edge[++idx] = v;
cap[idx] = w;
succ[idx] = ver[u];
ver[u] = idx;
edge[++idx] = u;
cap[idx] = 0;
succ[idx] = ver[v];
ver[v] = idx;
}
void update()
{
int x = t;
while(x != s)
{
int i = pre[x];
cap[i] -= incf[t];
cap[i ^ 1] += incf[t];
x = edge[i ^ 1];
}
maxflow += incf[t];
}
bool bfs()
{
memset(st,0,sizeof st);
queue<int> q;q.push(s);st[s] = 1;
incf[s] = INF;
while(!q.empty())
{
int u = q.front();q.pop();
for(int i = ver[u];i;i = succ[i])
{
int j = cap[i];
if(j)
{
int v = edge[i];
if(st[v]) continue;
incf[v] = min(incf[u],1ll*j);
pre[v] = i;
q.push(v);
st[v] = 1;
if(v == t) return 1;
}
}
}
return 0;
}
int main()
{
scanf("%d%d%d%d",&n,&m,&s,&t);
while(m--)
{
int u,v,c;scanf("%d%d%d",&u,&v,&c);
add(u,v,c);
}
while(bfs()) update();
printf("%lld",maxflow);
return 0;
}
dinic(当前弧优化)
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <iostream>
#include <queue>
#include <set>
#include <map>
using namespace std;
typedef long long ll;
const int N = 20000,M = 100000 * 2,INF = 1 << 29;
int edge[M],succ[M],cap[M],ver[N],idx;
int n,m,s,t,d[N],pre[N],now[N];
ll incf[N],maxflow;
int q[M],hh,tt;
void add(int u,int v,int w)
{
edge[idx] = v;
cap[idx] = w;
succ[idx] = ver[u];
ver[u] = idx++;
edge[idx] = u;
cap[idx] = 0;
succ[idx] = ver[v];
ver[v] = idx++;
}
bool bfs()
{
memset(d,0,sizeof d);
hh = 0,tt = -1;
q[++tt] = s;d[s] = 1;now[s] = ver[s];
while(hh <= tt)
{
int u = q[hh++];
for(int i = ver[u];~i;i = succ[i])
{
int v = edge[i];
if(cap[i] && !d[v])
{
q[++tt] = v;
now[v] = ver[v];
d[v] = d[u] + 1;
if(v == t) return 1;
}
}
}
return 0;
}
int dinic(int u,int limit)
{
if(u == t) return limit;
int flow = 0,k;
for(int i = now[u];~i && flow < limit;i = succ[i])
{
now[u] = i;
int v = edge[i];
if(cap[i] && d[v] == d[u] + 1)
{
k = dinic(v,min(limit - flow,cap[i]));
if(!k) d[v] = -1;
cap[i] -= k;
cap[i ^ 1] += k;
flow += k;
}
}
return flow;
}
int main()
{
memset(ver,-1,sizeof ver);
scanf("%d%d%d%d",&n,&m,&s,&t);
while(m--)
{
int u,v,c;scanf("%d%d%d",&u,&v,&c);
add(u,v,c);
}
int flow = 0;
while(bfs())
while(flow = dinic(s,INF))
maxflow += flow;
printf("%lld",maxflow);
return 0;
}
#无源汇上下界可行流
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 405,M = 10200 * 4,INF = 1 << 29;
int edge[M],succ[M],caplow[M],cap[M],ver[N],idx;
int n,m,s,t,d[N],pre[N],sub[N];
ll incf[N],maxflow;
queue<int> q;
void add(int u,int v,int wlow,int wup)
{
edge[idx] = v;
cap[idx] = wup - wlow;
caplow[idx] = wlow;
succ[idx] = ver[u];
ver[u] = idx++;
edge[idx] = u;
cap[idx] = 0;
succ[idx] = ver[v];
ver[v] = idx++;
}
bool bfs()
{
memset(d,0,sizeof d);
while(q.size()) q.pop();
q.push(s);d[s] = 1;
while(!q.empty())
{
int u = q.front();q.pop();
for(int i = ver[u];i;i = succ[i])
{
int v = edge[i];
if(cap[i] && !d[v])
{
q.push(v);
d[v] = d[u] + 1;
if(v == t) return 1;
}
}
}
return 0;
}
int dinic(int u,int flow)
{
if(u == t) return flow;
int rest = flow,k,i;
for(int i = ver[u];i && rest;i = succ[i])
{
int v = edge[i];
if(cap[i] && d[v] == d[u] + 1)
{
k = dinic(v,min(rest,cap[i]));
if(!k) d[v] = 0;
cap[i] -= k;
cap[i ^ 1] += k;
rest -= k;
}
}
return flow - rest;
}
int main()
{
memset(ver,-1,sizeof ver);
scanf("%d%d",&n,&m);
s = 0;t = n + 1;
for(int i = 0;i < m;++i)
{
int a,b,c,d;scanf("%d%d%d%d",&a,&b,&c,&d);
sub[a] -= c;sub[b] += c;
add(a,b,c,d);
}
ll allflow = 0;
for(int i = 1;i <= n;++i)
{
if(sub[i] > 0) add(s,i,0,sub[i]),allflow += sub[i];
else if(sub[i] < 0) add(i,t,0,-sub[i]);
}
int flow = 0;
while(bfs())
while(flow = dinic(s,INF))
maxflow += flow;
if(allflow == maxflow)
{
puts("YES");
for(int i = 0;i < m * 2;i += 2)
{
int u = edge[i],v = edge[i ^ 1];
if(u == s || u == t || v == u || v == t) continue;
printf("%d\n",cap[i ^ 1] + caplow[i]);
}
}
else puts("NO");
return 0;
}
有源汇上下界最大流
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <iostream>
#include <queue>
#include <set>
#include <map>
using namespace std;
typedef long long ll;
const int N = 20000,M = 100000 * 2,INF = 1 << 29;
int edge[M],succ[M],cap[M],ver[N],idx;
int n,m,s,t,d[N],pre[N],now[N],sub[N];
ll incf[N],maxflow;
int q[M],hh,tt;
void add(int u,int v,int w)
{
edge[idx] = v;
cap[idx] = w;
succ[idx] = ver[u];
ver[u] = idx++;
edge[idx] = u;
cap[idx] = 0;
succ[idx] = ver[v];
ver[v] = idx++;
}
bool bfs()
{
memset(d,0,sizeof d);
hh = 0,tt = -1;
q[++tt] = s;d[s] = 1;now[s] = ver[s];
while(hh <= tt)
{
int u = q[hh++];
for(int i = ver[u];~i;i = succ[i])
{
int v = edge[i];
if(cap[i] && !d[v])
{
q[++tt] = v;
now[v] = ver[v];
d[v] = d[u] + 1;
if(v == t) return 1;
}
}
}
return 0;
}
int dinic(int u,int limit)
{
if(u == t) return limit;
int flow = 0,k;
for(int i = now[u];~i && flow < limit;i = succ[i])
{
now[u] = i;
int v = edge[i];
if(cap[i] && d[v] == d[u] + 1)
{
k = dinic(v,min(limit - flow,cap[i]));
if(!k) d[v] = -1;
cap[i] -= k;
cap[i ^ 1] += k;
flow += k;
}
}
return flow;
}
int main()
{
memset(ver,-1,sizeof ver);
int S,T;scanf("%d%d%d%d",&n,&m,&S,&T);
s = 0,t = n + 1;
while(m--)
{
int a,b,c,d;scanf("%d%d%d%d",&a,&b,&c,&d);
add(a,b,d - c);
sub[a] -= c;sub[b] += c;
}
ll allflow = 0;
for(int i = 1;i <= n;++i)
if(sub[i] > 0) add(s,i,sub[i]),allflow += sub[i];
else if(sub[i] < 0) add(i,t,-sub[i]);
add(T,S,INF);
int flow;
while(bfs())
while(flow = dinic(s,INF))
maxflow += flow;
if(maxflow < allflow) puts("No Solution");
else
{
int pres = cap[idx - 1];
cap[idx - 1] = cap[idx - 2] = 0;
flow = 0;maxflow = 0;
s = S;t = T;
while(bfs())
while(flow = dinic(s,INF))
maxflow += flow;
printf("%lld",pres + maxflow);
}
return 0;
}
有源汇上下界最小流
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <iostream>
#include <queue>
#include <set>
#include <map>
using namespace std;
typedef long long ll;
const int N = 50070,M = 125003 * 4,INF = 2147483647;
int edge[M],succ[M],cap[M],ver[N],idx;
int n,m,s,t,d[N],pre[N],now[N],sub[N];
ll incf[N],maxflow;
int q[M],hh,tt;
void add(int u,int v,int w)
{
edge[idx] = v;
cap[idx] = w;
succ[idx] = ver[u];
ver[u] = idx++;
edge[idx] = u;
cap[idx] = 0;
succ[idx] = ver[v];
ver[v] = idx++;
}
bool bfs()
{
memset(d,0,sizeof d);
hh = 0,tt = -1;
q[++tt] = s;d[s] = 1;now[s] = ver[s];
while(hh <= tt)
{
int u = q[hh++];
for(int i = ver[u];~i;i = succ[i])
{
int v = edge[i];
if(cap[i] && !d[v])
{
q[++tt] = v;
now[v] = ver[v];
d[v] = d[u] + 1;
if(v == t) return 1;
}
}
}
return 0;
}
int dinic(int u,int limit)
{
if(u == t) return limit;
int flow = 0,k;
for(int i = now[u];~i && flow < limit;i = succ[i])
{
now[u] = i;
int v = edge[i];
if(cap[i] && d[v] == d[u] + 1)
{
k = dinic(v,min(limit - flow,cap[i]));
if(!k) d[v] = -1;
cap[i] -= k;
cap[i ^ 1] += k;
flow += k;
}
}
return flow;
}
int main()
{
memset(ver,-1,sizeof ver);
int S,T;scanf("%d%d%d%d",&n,&m,&S,&T);
s = 0,t = n + 1;
while(m--)
{
int a,b,c,d;scanf("%d%d%d%d",&a,&b,&c,&d);
add(a,b,d - c);
sub[a] -= c;sub[b] += c;
}
ll allflow = 0;
for(int i = 1;i <= n;++i)
if(sub[i] > 0) add(s,i,sub[i]),allflow += sub[i];
else if(sub[i] < 0) add(i,t,-sub[i]);
add(T,S,INF);
int flow;
while(bfs())
while(flow = dinic(s,INF))
maxflow += flow;
// cout << maxflow << endl;
if(maxflow < allflow) puts("No Solution");
else
{
int pres = cap[idx - 1];
cap[idx - 1] = cap[idx - 2] = 0;
flow = 0;maxflow = 0;
s = T;t = S;
while(bfs())
while(flow = dinic(s,INF))
maxflow += flow;
printf("%lld",pres - maxflow);
}
return 0;
}